// @algorithm @lc id=629 lang=cpp 
// @title k-inverse-pairs-array


// @test(3,0)=1
// @test(3,1)=2
#define mod 1000'000'007
class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(2, vector<int>(k+1, 0));
        dp[0][0] = 1;
        for(int i=1; i<=n; i++){
            for(int j=0; j<=k; j++){
                auto & cur = dp[i&1];
                auto & pre = dp[1-(i&1)];
                cur[j] = (j<1?0:cur[j-1]) - (j<i?0:pre[j-i]) + pre[j];
                if(cur[j] >= mod) cur[j] -= mod;
                else if(cur[j]<0) cur[j] += mod;
            }
        }
        return dp[n&1][k];
    }
};